package first.forHuaWei.codeTop;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName LC15
 * @description:
 * @author: 荣燊
 * @create: 2021-09-13 10:50
 **/
public class LC15 {
    // 三数之和，重点在去重
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int n = nums.length;
        if (n < 3) {
            return lists;
        }

        Arrays.sort(nums);

        for (int i=0; i<n-2; i++) {
            if (nums[i] > 0) {
                break;
            }
            // 去重
            if (i>0 && nums[i] == nums[i-1]) {
                continue;
            }
            // 双指针
            int k = i+1;
            int j = n-1;
            while (k < j) {
                int temp = nums[i]+nums[k]+nums[j];
                if (temp < 0) {
                    // 去重
                    while (k<j && nums[k] == nums[++k]);
                } else if (temp > 0) {
                    // 去重
                    while (k<j && nums[j] == nums[--j]);
                } else {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[k]);
                    list.add(nums[j]);
                    lists.add(list);
                    // 去重，此时while循环若还没结束的话
                    while (k<j && nums[k] == nums[++k]);
                    while (k<j && nums[j] == nums[--j]);
                }
            }
        }
        return lists;
    }

    //
    public static void main(String[] args) {

    }
}
